#include <iostream>
#include <algorithm>
#include <random>
#include <ctime>
#include <vector>
#include "BinarySearchTree.h"

/**
 *@breif 用来将输入的特定vector构建成二叉树的形式
 *在函数内部我定义了一个二叉树类实例rng，用以对_arr内部数据进行排序，当_mode = 0时，无需对_arr内部数据做任何修改，直接通过for，以及BinarySearchTree的公共函数insert构建出一株二叉树;当_mode = 1时，先通过random_shuffle对_arr内部数据乱序后，再重复前述操作构建二叉树。
 *@param[in] _arr 为待排序的输入vector
 *@param[in] _mode 为vector是否需事先乱序的判断标准
 *@note 当且仅当输入的_mode = 0时，不对vector中的数据进行乱序，其他情况均会先乱序后排序。
 */
template <typename Comparable>
void BSTSorting( const std::vector<Comparable> &_arr, int _mode = 0 )
{
  int i = 0;
  BinarySearchTree<Comparable> rng;
  std::vector<Comparable> rhs = _arr;
  
  if( !_mode )
    {
      for(i = 0; i < rhs.size(); i++)
	rng.insert(rhs[i]);
    }
  else
    {
      srand((unsigned int)time(0));
      random_shuffle(rhs.begin(),rhs.end()); ///将vector中的数据进行乱序
      for(i = 0; i < rhs.size(); i++)
	rng.insert(rhs[i]);
    }
}

/**
 *@breif 用来将输入的特定vector构建成二叉树的形式
 *首先利用while循环生成一个顺序的vector，然后通过ctime头文件引入\verb|clock_t、CLOCKS_PER_SEC|用以计算排序算法的效率，并且直接输出duration。
 *@param[in] length 为自动生成测试样例vector的长度
 *@param[in] times 为重复实验的次数
 */
void Test( const int & length, int times )
{
  std::cout << "列表长度：" << length << ",重复实验:" << times << std::endl;
  clock_t start, finish;
  double duration;
  std::vector<int> vec;
  int i = 0;
  while(i < length)
    {vec.push_back(i);i++;}
  start = clock();
  BSTSorting(vec, 0);
  finish = clock();
  duration = (double)(finish - start) / CLOCKS_PER_SEC;
  std::cout << "不乱序最坏效率为：" << duration << std::endl;
  duration = 0; 
  for( i = 0; i < times; i++ )
    {
      start = clock();
      BSTSorting(vec, 1);
      finish = clock();
      duration += (double)(finish - start) / CLOCKS_PER_SEC;
    }
  std::cout << "乱序后平均效率为：" << duration/times << std::endl;
}

int main()
{
  int length, times;
  Test(10, 10);
  Test(100, 10);
  Test(1000, 10);
  Test(10000, 10);
  Test(100000, 10);
  Test(1000, 100);
  Test(1000, 1000);
  Test(1000, 10000);
  Test(1000, 100000);
  std::cout << "输入数据如“10 10”来测试，退出即输入0。" << std::endl;
  while( 1 )
    {
      std::cin >> length;
      if( length == 0 ) break;
      std::cin >> times;
      Test(length, times);
    }
  
  return 0;
}
